# 左孩子右兄弟(好题, 动态规划)


def bin_tree_height(arr):
    n = len(arr)
    # 构造树结构, 每个节点存储它下面的子节点
    tree = [[] for _ in range(n + 1)]
    for i in range(n):
        tree[arr[i]].append(i + 2)

    dp = [0] * (n + 2)  # dp[i]表示以i节点为根节点的子树的高度
    for i in range(n, 0, -1):  # 从末尾开始求每个节点作为根节点的最大高度是多少
        max_height = 0
        for j in tree[i]:  # 遍历i节点的所有子节点
            max_height = max(max_height, dp[j])  # 求出子节点中的最大高度
        dp[i] = max_height + len(tree[i])  # i节点的最大高度 = 子节点数量 + 子节点的最大高度
    return dp[1]


if __name__ == '__main__':
    print(bin_tree_height([1, 1, 1, 2]))
